package structures.tree;

// 线索化二叉树
public class ThreadedBinaryDemo {
    public static void main(String[] args) {
        ThreadedNode node1 = new ThreadedNode(1, "name1");
        ThreadedNode node2 = new ThreadedNode(2, "name2");
        ThreadedNode node3 = new ThreadedNode(3, "name3");
        ThreadedNode node4 = new ThreadedNode(4, "name4");
        ThreadedNode node5 = new ThreadedNode(5, "name5");
        ThreadedBinary threadedBinary = new ThreadedBinary(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        threadedBinary.infixOrder();
        threadedBinary.threadedBinary();
        System.out.println("---------------------");
        System.out.println(node5.getLeft());
        System.out.println(node5.getRight());
        System.out.println("---------------------");
        threadedBinary.threadOrder();
    }
}

class ThreadedBinary {
    ThreadedNode root;
    ThreadedNode preNode;

    public ThreadedBinary(ThreadedNode root) {
        this.root = root;
    }

    public void threadedBinary() {
        threadedBinary(root);
    }

    // 遍历线索化二叉树的方法
    public void threadOrder() {
        ThreadedNode node = root;
        while (node != null) {
            while (!node.isThreadedLeft()) {
                node = node.getLeft();
            }
            System.out.println(node);

            while (node.isThreadedRight()) {
                node = node.getRight();
                System.out.println(node);
            }

            node = node.getRight();
        }
    }

    // 对二叉树进行中序线索化
    private void threadedBinary(ThreadedNode node) {
        if (node == null) {
            return;
        }
        // 左
        threadedBinary(node.getLeft());
        // 中
        if (node.getLeft() == null) {
            node.setLeft(preNode);
            node.setThreadedLeft(true);
        }

        if (preNode != null && preNode.getRight() == null) {
            preNode.setRight(node);
            preNode.setThreadedRight(true);
        }

        preNode = node;
        
        // 右
        threadedBinary(node.getRight());
    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        infixOrder(root);
    }

    private void infixOrder(ThreadedNode root) {
        root.infixOrder();
    }
}

class ThreadedNode {
    private int id;
    private String name;
    private ThreadedNode left;
    private ThreadedNode right;
    private boolean isThreadedLeft = false;
    private boolean isThreadedRight = false;

    public ThreadedNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public void infixOrder() {
        if (this.getLeft() != null) {
            this.getLeft().infixOrder();
        }

        System.out.println(this);

        if (this.getRight() != null) {
            this.getRight().infixOrder();
        }
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ThreadedNode getLeft() {
        return left;
    }

    public void setLeft(ThreadedNode left) {
        this.left = left;
    }

    public ThreadedNode getRight() {
        return right;
    }

    public void setRight(ThreadedNode right) {
        this.right = right;
    }

    public boolean isThreadedLeft() {
        return isThreadedLeft;
    }

    public void setThreadedLeft(boolean threadedLeft) {
        isThreadedLeft = threadedLeft;
    }

    public boolean isThreadedRight() {
        return isThreadedRight;
    }

    public void setThreadedRight(boolean threadedRight) {
        isThreadedRight = threadedRight;
    }

    @Override
    public String toString() {
        return "ThreadedNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
